package LetCode;

/**
 * @author: lwt
 * @date: 2025/7/25 9:12
 * @description:
 *
 * 多数元素
 *
 * 找出一个数组中出现次数超过n/2的元素
 */
public class day4 {
    public static void main(String[] args) {
        int[] nums = {8,8,7,7,7};
//        int[] nums = {2,2,1,1,1,2,2};
//        int[] nums = {6,5,5};
        int i = majorityElement(nums);
        System.out.println(i);
    }

    public static int majorityElement(int[] nums) {
//            int n = nums.length;  // [3,2,3]  输出 3
//            if (n==0) return 0;
//            int slow = 0;   //慢指针
//            int fast = slow+1;   //快指针
//            int index = 0;  //出现次数
//            int s;
//            while (fast < n) {
//                if (nums[slow] == nums[fast]) {
//                    index++;
//                    if (index > n/2) {
//                        break;
//                    }
//                }
//            }
//            s = nums[slow];
//            return s;


        /**
         * 摩尔投票法
         * 基本思路：每一轮投票的过程中，从数组中找到一对不同的元素，将其从数组中删除
         * 定义接收器result  计数器count
         * 如果count==0；将0处的值赋给result count置为1
         * 如果count不为0，如果当前元素等于result,count++,否则count--
         * 遍历结束后，result则为重复出现次数最多的元素
         * */
        int result = 0;
        int count = 0;
        for (int i  =0;i< nums.length;i++){
            if (count == 0){
                result = nums[i];
                count =1;
            }else if (nums[i] == result){
                count+=1;
            } else {
                count-=1;
            }
        }
        return  result;



//        int s = 0;
//        for (int i = 0; i < nums.length; i++) {
//            int index = 0;
//            for (int j = i; j< nums.length; j++) {
//                if (nums[j] == nums[i]) {
//                    index ++;
//                }
//            }
//            if (index>nums.length/2) {
//                s= nums[i];
//                break;
//            }
//        }
//        return s;
    }
}
